#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
  ListNode *sum_head = nullptr, *sum_tail = nullptr;
  int a = 0, p = 0;
  while (l1 != nullptr && l2 != nullptr) {
    a = l1->val + l2->val + p;
    p = 0;
    if (a > 9) {
      a = a - 10;
      p = 1;
    }
    if (sum_head == nullptr) {
      sum_head = new ListNode(a);
      sum_tail = sum_head;
    } else {
      sum_tail->next = new ListNode(a);
      sum_tail = sum_tail->next;
    }
    l1 = l1->next;
    l2 = l2->next;
  }

  while (l1 != nullptr) {
    a = l1->val + p;
    p = 0;
    if (a > 9) {
      a = a - 10;
      p = 1;
    }
    sum_tail->next = new ListNode(a);
    sum_tail = sum_tail->next;
    l1 = l1->next;
  }

  while (l2 != nullptr) {
    a = l2->val + p;
    p = 0;
    if (a > 9) {
      a = a - 10;
      p = 1;
    }
    sum_tail->next = new ListNode(a);
    sum_tail = sum_tail->next;
    l2 = l2->next;
  }
  if (p == 1) {
    sum_tail->next = new ListNode(1);
  }
  return sum_head;
}

ListNode *buildList(vector<int> &v) {
  ListNode *head = nullptr, *tail = nullptr;
  for (int i = 0; i < v.size(); i++) {
    if (head == nullptr) {
      head = new ListNode(v[i]);
      tail = head;
    } else {
      tail->next = new ListNode(v[i]);
      tail = tail->next;
    }
  }
  return head;
}

void print(ListNode *head) {
  while (head != nullptr) {
    cout << head->val << " ";
    head = head->next;
  }
  cout << endl;
}

int main() {
  vector<int> v1{9, 9, 9, 9, 9, 9, 9};
  ListNode *l1 = buildList(v1);
  vector<int> v2{9, 9, 9, 9};
  ListNode *l2 = buildList(v2);
  print(l1);
  print(l2);
  ListNode *l3 = addTwoNumbers(l1, l2);
  print(l3);
  return 0;
}